home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / jcool01.zip / BASE_LIS.C < prev    next >
C/C++ Source or Header  |  1992-08-14  |  47KB  |  1,362 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. // Created: MJF 03/27/89 -- Initial design and implementation.
  13. // Updated: MJF 04/15/89 -- Implemented Base list class.
  14. // Updated: JCB 06/05/89 -- Fixed merge and sort.
  15. // Updated: JCB 06/20/89 -- Implemented next_union, next_intersection,
  16. //                          next_difference, next_xor.
  17. // Updated: JCB 06/21/89 -- Modified next() and prev() to check for a current
  18. //                          position not in THIS list, i.e. !traversal
  19. // Updated: MJF 08/03/89 -- Improved operator== by checking for identical nodes
  20. // Updated: MJF 08/10/89 -- Changed return values of operator+=, etc to List ref
  21. // Updated: MJF 08/11/89 -- Changed methods which return new list references:
  22. //                          tail, last, but_last, member, sublist and copy
  23. // Updated: LGO 09/07/89 -- Made next, reference and dereference inline
  24. // Updated: LGO 09/07/89 -- Moved the guts of find to the template classes.
  25. // Updated: LGO 09/08/89 -- use do_find instead of compare_data in most places.
  26. // Updated: LGO 09/08/89 -- Move push to the template classes.
  27. // Updated: MBN 09/20/89 -- Added conditional exception handling
  28. // Updated: LGO 10/05/89 -- Don't sort lists with less than 2 elements
  29. // Updated: MBN 10/11/89 -- Change "current_position" to "curpos" and also
  30. //                          "previous_position" to "prevpos"
  31. // Updated: LGO 12/04/89 -- Make binary set operators not inline
  32. // Updated: LGO 12/05/89 -- Make sort/merge predicate ANSI compatable
  33. // Updated: MJF 03/12/90 -- Added group names to RAISE
  34. // Updated: MJF 05/22/90 -- Fixed remove_duplicates
  35. // Updated:  VDN 02/21/92 -- new lite version and fix memory leaks
  36. // Updated: JAM 08/14/92 -- removed DOS specifics, stdized #includes
  37. // Updated: JAM 08/14/92 -- modernized template syntax, remove macro hacks
  38. //
  39. // This  file contains member and friend  function implementation code for  the
  40. // CoolList class defined in the  Base_List.h header  file.  Where appropriate  and
  41. // possible, interfaces  to, and  us of,  existing system   functions has  been
  42. // incorporated.  An overview of the structure of the CoolList class, along  with a
  43. // synopsis of each member and friend function, can be found in the Base_List.h
  44. // header file.
  45.  
  46. #ifndef BASE_LISTH                // If CoolBase_List class not defined,
  47. #include <cool/Base_List.h>            // include header file
  48. #endif
  49.  
  50. CoolBase_List NIL = CoolBase_List();            // NIL -- Global NIL CoolBase_List
  51.  
  52. // CoolBase_List_Node() -- Constructor
  53. // Input:         None
  54. // Output:        None
  55.  
  56. CoolBase_List_Node::CoolBase_List_Node() {}        // Constructor
  57.  
  58.  
  59. // ~CoolBase_List_Node -- Destructor (not inline because it's virtual)
  60. //                   Virtual is needed to call ~CoolList_Node<Type>.
  61. // Input:         None
  62. // Output:        None
  63.  
  64. CoolBase_List_Node::~CoolBase_List_Node() {;}
  65.  
  66.  
  67. // get_data()  -- Gets data of node. There is no data for CoolBase_List class.
  68. // Input:         None.
  69. // Output:        A void* pointer.
  70.  
  71. const void* CoolBase_List_Node::get_data() {
  72.   cout << "\nWarning:  CoolBase_List_Node::get_data() has been called.\n";
  73.   return NULL;
  74. }
  75.  
  76.  
  77. // set_data()  -- Sets data of node to specified value. There is not data
  78. //                to set for CoolBase_List class.
  79. // Input:         A void* pointer.
  80. // Output:        None.
  81.  
  82. void CoolBase_List_Node::set_data(const void*) {
  83. #if ERROR_CHECKING
  84.   //RAISE (Warning, SYM(CoolBase_List_Node), SYM(Redundant_Method_Call),
  85.   printf ("CoolBase_List_Node::set_data(): Method called is redundant.\n");
  86. #endif
  87. }
  88.  
  89.  
  90. // ~CoolBase_List -- Destructor (not inline because it's virtual)
  91. // Input:         None
  92. // Output:        None
  93.  
  94. CoolBase_List::~CoolBase_List () {;}
  95.  
  96. // Prev() -- decrement current position. If NULL, set it to last.
  97. // Input:    None.
  98. // Output:   TRUE or FALSE.
  99.  
  100. Boolean CoolBase_List::prev() {
  101.   register CoolBase_List_Node* cp = this->curpos;
  102.   CoolBase_List_Node* prev = this->prevpos;
  103.   // if cp invalid (i.e. NULL) the following test will fail
  104.   if (prev != NULL && prev->next == cp) {
  105.     // already have the previous position
  106.     cp = prev;
  107.     this->prevpos = NULL; // this isn't needed, but why not...
  108.   } else {
  109.     // find previous node of current position
  110.     // When cp is invalid, this finds the last node.
  111.     register CoolBase_List_Node* np = this->node_ptr;
  112.     prev = NULL;
  113.     if (np != NULL) {
  114.       while(np->next != cp)
  115.     prev = np, np = np->next;
  116.       cp = np;
  117.       this->prevpos = prev;    
  118.     }
  119.   }
  120.   // current position not found in CoolBase_List
  121.   return (this->curpos = cp) != NULL;
  122. }
  123.  
  124. // operator== -- Returns TRUE if similar data in THIS and the specified CoolBase_List.
  125. //               Uses the static CoolBase_List comparer function on elements.
  126. // Input:        A CoolBase_List reference.
  127. // Output:       TRUE or FALSE.
  128.  
  129. Boolean CoolBase_List::operator==(const CoolBase_List& l) const {
  130.   if (this == &l) return TRUE;  // same CoolBase_Lists
  131.   for (CoolBase_List_Node *np = this->node_ptr, *np_l = l.node_ptr;
  132.       np != NULL && np_l != NULL; 
  133.       np = np->next, np_l = np_l->next) {
  134.     if (np == np_l)
  135.       return TRUE;   // same node pointers
  136.     else if (!this->compare_data(np->get_data(), np_l->get_data()))
  137.       return FALSE;
  138.   }
  139.   if (np == NULL && np_l == NULL) return TRUE;
  140.   else return FALSE;
  141. }
  142.  
  143.  
  144. // tail() -- Sets CoolBase_List passed to the the nth tail of this CoolBase_List. With no 2nd
  145. //           argument, tail() sets CoolBase_List passed to the 1st tail of this CoolBase_List.
  146. // Input:    A CoolBase_List reference to store the nth tail elements of THIS and
  147. //           the positive integer, n. (default 1)
  148. // Output:   None.
  149.  
  150. void CoolBase_List::tail(CoolBase_List& l, int n) {
  151.   this->dereference(l.node_ptr);
  152.   int count = n;
  153.   CoolBase_List_Node* np;
  154.   for (np = this->node_ptr; np != NULL && count > 0; np = np->next, count--);
  155.   // if n < length, return nth tail
  156.   if (np != NULL && count == 0) {
  157.     this->curpos = np;
  158.     this->reference(np);
  159.     l.node_ptr = np;
  160.   }
  161.   else l.node_ptr = NULL;
  162. }
  163.  
  164.  
  165. // last() -- Sets CoolBase_List passed to the n last elements of this CoolBase_List. With no
  166. //           2nd argument, sets CoolBase_List passed to the last element of thie CoolBase_List.
  167. // Input:    A CoolBase_List reference to store the n last elements of THIS and
  168. //           the positive interger, n (default 1).
  169. // Output:   None.
  170.  
  171. void CoolBase_List::last(CoolBase_List& l, int n) {
  172.   // last n elements = (size-n)th tail
  173.   int nth = this->length() - n;   
  174.   if (nth >= 0)
  175.     tail(l, nth);
  176.   else {
  177.     this->dereference(l.node_ptr);
  178.     l.node_ptr = NULL;
  179.   }
  180. }
  181.  
  182.  
  183. // but_last() -- Sets CoolBase_List passed to all but the last n elements of THIS List. 
  184. //               With no 2nd argument, sets CoolBase_List passed to all but the last
  185. //               element
  186. // Input:        A positive integer (default 1).
  187. // Output:       An altered THIS with all but the n last elements.
  188.  
  189. void CoolBase_List::but_last(CoolBase_List& l, int n) {
  190.   this->reset();                // Current position invalid
  191.   CoolBase_List_Node* np = this->node_ptr;
  192.   this->dereference(l.node_ptr);        // Delete nodes in l
  193.   if (n == 0) {
  194.     this->reference(np);            
  195.     l.node_ptr = np;                // Points at all nodes of THIS
  196.   }
  197.   else {
  198.     // get the number of nodes in this CoolBase_List and copy into CoolBase_List l
  199.     int no_nodes = this->length() - n; 
  200.     if (no_nodes > 0 && np != NULL)  {
  201.       CoolBase_List_Node* first_np = this->insert_after_node(np->get_data(), NULL);
  202.       CoolBase_List_Node* rest_np = first_np;    
  203.       no_nodes--;
  204.       for(np = np->next; 
  205.       np != NULL && no_nodes > 0; 
  206.       np = np->next, no_nodes--) {
  207.     rest_np = this->insert_after_node(np->get_data(), rest_np);
  208.       }
  209.       l.node_ptr = first_np;            // Create totally new nodes
  210.     } else
  211.       l.node_ptr = NULL;
  212.   }
  213. }
  214.  
  215.  
  216. // clear() -- Removes all nodes of THIS CoolBase_List.
  217. // Input:     None.
  218. // Output:    None.
  219.  
  220. void CoolBase_List::clear() {
  221.   this->reset();                // make current position invalid   
  222.   this->dereference(this->node_ptr);        // Delete nodes in this.
  223.   this->node_ptr = NULL;
  224. }
  225.  
  226.  
  227. // length() -- Returns the number of elements in THIS CoolBase_List.
  228. // Input:      None.
  229. // Output:     An interger representing the number of elements in THIS.
  230.  
  231. int CoolBase_List::length() {
  232.   int count = 0;
  233.   for (CoolBase_List_Node* np = this->node_ptr; np != NULL; np = np->next, count++);
  234.   return count;
  235. }
  236.  
  237.  
  238. // position -- Returns current position.
  239. // Input:      THIS.
  240. // Output:     An integer representing current position.
  241.  
  242. int CoolBase_List::position() {
  243.   if (this->curpos == NULL) return -1;
  244.   int index = 0;
  245.   for (CoolBase_List_Node* np = this->node_ptr;  np != NULL; np = np->next, index++)
  246.     if (np == this->curpos) return index;
  247.   return -1;
  248. }
  249.  
  250. // search() -- Returns TRUE if the specified CoolBase_List is a subset of this CoolBase_List
  251. // Input:      A reference to subList to be searched.
  252. // Output:     TRUE or FALSE.
  253.  
  254. Boolean CoolBase_List::search(const CoolBase_List& l) {
  255.   CoolBase_List_Node* tnode = this->node_ptr;
  256.   CoolBase_List_Node* lnode = l.node_ptr;
  257.   if (tnode == lnode) {
  258.     // this CoolBase_List and subList l have same head node pointers
  259.     this->curpos = tnode;
  260.     this->prevpos = NULL;
  261.     return TRUE;  
  262.   }
  263.   if (lnode == NULL) return FALSE;    // subList l is nil
  264.   while(tnode != NULL &&
  265.     this->do_find(tnode, lnode->get_data(), this->curpos, this->prevpos)) {
  266.     tnode = this->curpos;
  267.     if (tnode == lnode) {
  268.       // a node in this CoolBase_List and head node of CoolBase_List l are same
  269.       return TRUE;
  270.     }
  271.     // data of node in this CoolBase_List is also in node of CoolBase_List l
  272.     // continue searching rest of data
  273.     for (CoolBase_List_Node *np2 = tnode->next, *lnp = lnode->next; 
  274.      np2 != NULL && lnp != NULL;
  275.      np2 = np2->next, lnp = lnp->next) {
  276.       if (np2 == lnp) {
  277.     // node in this CoolBase_List and node in CoolBase_List l are same
  278.     return TRUE;
  279.       }
  280.       if  (!this->compare_data(np2->get_data(), lnp->get_data()))
  281.     break;
  282.     }
  283.     if (lnp == NULL) {
  284.       // found data of CoolBase_List l in this CoolBase_List
  285.       return TRUE;
  286.     }
  287.     tnode = tnode->next;
  288.   } 
  289.   return FALSE;
  290. }
  291.  
  292.  
  293. // sublist() -- Returns TRUE if THIS CoolBase_List contains second argument and sets
  294. //              first argument to a sublist in THIS CoolBase_List starting at the 1st
  295. //              occurence of second argument.
  296. // Input:       A reference to the CoolBase_List which will be set to a sublist within
  297. //              THIS CoolBase_List; and a reference to the CoolBase_List in search of.
  298. // Output:      TRUE or FALSE.
  299.  
  300. Boolean CoolBase_List::sublist(CoolBase_List& l, const CoolBase_List& subl) {
  301.   this->dereference(l.node_ptr);
  302.   if (this->search(subl)) {
  303.     this->reference(this->curpos);
  304.     l.node_ptr = this->curpos;  
  305.     return TRUE;
  306.   } else {
  307.     l.node_ptr = NULL;
  308.     return FALSE;
  309.   }
  310. }
  311.  
  312.  
  313. // copy() -- Mutates *this to store a copy of elements in specified List
  314. // Input:    List containing elements to be copied from
  315. // Output:   None.
  316.  
  317. void CoolBase_List::copy (const CoolBase_List& l) {
  318.   cout << "****warning: copy from argument into *this****" << endl;
  319.   this->reset();                // make current position invalid
  320.   this->dereference(this->node_ptr);        // free current nodes of *this
  321.   CoolBase_List_Node* np = l.copy_nodes();        // make new list of nodes of l
  322.   this->node_ptr = np;                // all with ref_count = 1
  323. }
  324.  
  325. // reverse() -- Reverses the order of the elements of THIS CoolBase_List.
  326. // Input:       None.
  327. // Output:      None.
  328.  
  329. void CoolBase_List::reverse() {
  330.   this->reset();                // Current position invalid
  331.   CoolBase_List_Node *np, *np2, *rev_head;
  332.   rev_head = NULL;
  333.   for (np = this->node_ptr; np != NULL; np = np2) {
  334.     np2 = np->next;
  335.     np->next = rev_head;
  336.     rev_head = np;
  337.   }
  338.   this->node_ptr = rev_head;
  339. }
  340.  
  341.  
  342. // prepend() -- Prepends the specified CoolBase_List to the front of this CoolBase_List and
  343. //              returns TRUE if specified CoolBase_List is not NULL
  344. // Input:       A reference to the CoolBase_List to be prepended.
  345. // Output:      Always TRUE.
  346.  
  347. Boolean CoolBase_List::prepend(const CoolBase_List& l) {
  348.   // first get copy of nodes in CoolBase_List l 
  349.   CoolBase_List_Node* lnode = l.copy_nodes();
  350.   if (lnode == NULL)
  351.     return FALSE;
  352.   // now prepend copy of l to front of THIS CoolBase_List.  
  353.   this->curpos = lnode;
  354.   this->prevpos = NULL;
  355.   CoolBase_List_Node* last_np = this->curpos;
  356.   if (last_np != NULL) {  
  357.     // find last node of new copy of l
  358.     while(last_np->next != NULL) last_np = last_np->next;
  359.     // insert last node of CoolBase_List l in front of head node of this CoolBase_List
  360.     // and set head node of this CoolBase_List to head node of CoolBase_List l
  361.     last_np->next = this->node_ptr;
  362.     this->node_ptr = this->curpos;
  363.   }
  364.   return TRUE;
  365. }
  366.  
  367.  
  368. // append() -- Appends the specified CoolBase_List to the end of this CoolBase_List and returns
  369. //             TRUE if specified CoolBase_List is not NULL.
  370. // Input:      A reference to the CoolBase_List to be appended.
  371. // Output:     TRUE or FALSE.
  372.  
  373. Boolean CoolBase_List::append(const CoolBase_List& l) {
  374.   CoolBase_List_Node* lnode = l.node_ptr;
  375.   if (lnode == NULL)
  376.     return FALSE;
  377.   this->curpos = lnode;                // curpos is head node of l
  378.   CoolBase_List_Node* last_np = this->node_ptr;
  379.   if (last_np == NULL) { 
  380.     // there are no nodes in this;
  381.     // just set head node of this CoolBase_List to head node of CoolBase_List l
  382.     this->node_ptr = this->curpos;
  383.     this->prevpos = NULL;
  384.   }
  385.   else {
  386.     // find last node of this
  387.     while(last_np->next != NULL) last_np = last_np->next;
  388.     // add head node of CoolBase_List l after last node of this CoolBase_List
  389.     last_np->next = this->curpos;
  390.     this->prevpos = last_np;
  391.   }
  392.   this->reference(this->curpos);
  393.   return TRUE;
  394. }
  395.  
  396.  
  397. // set_tail() -- Sets the nth tail of THIS CoolBase_List to the specified CoolBase_List
  398. // Input:        A CoolBase_List reference, and a count (default 1).
  399. // Output:       TRUE if nth tail exists, FALSE otherwise.
  400.  
  401. Boolean CoolBase_List::set_tail(const CoolBase_List& l, int n) {
  402.   // find node at start of nth tail
  403.   int count = n;
  404.   for (CoolBase_List_Node *np = this->node_ptr, *prev_np = NULL; 
  405.       np != NULL && count > 0;
  406.       prev_np = np, np = np->next, count--);
  407.   if (np != NULL && count == 0) {
  408.      this->curpos = l.node_ptr;    // Current position=head node
  409.      this->prevpos = prev_np;        // Previous position is nth-1
  410.      // replace nth node with head node of CoolBase_List l
  411.      if (prev_np == NULL) this->node_ptr = this->curpos; // when n=0
  412.      else prev_np->next = this->curpos;           // when n>0
  413.      this->reference(this->curpos);
  414.      // removing nth tail
  415.      this->dereference(np);
  416.      return TRUE;
  417.    }
  418.   return FALSE;
  419. }
  420.  
  421.  
  422. // remove_duplicates() -- Removes all duplicate elements in THIS CoolBase_List.
  423. // Input:                 None.
  424. // Output:                TRUE if at least one item is removed, FALSE otherwise.
  425.  
  426. Boolean CoolBase_List::remove_duplicates() {
  427.   Boolean success = FALSE;            // success flag
  428.   CoolBase_List_Node* np = this->node_ptr;
  429.   CoolBase_List_Node* np_next;
  430.   while ((np != NULL) && ((np_next = np->next) != NULL)) {
  431.     while (this->do_find (np_next, np->get_data(), this->curpos, this->prevpos))
  432.       {
  433.     this->dereference(this->remove());    // duplicate nodes go to trash
  434.     success = TRUE;
  435.     if ((np_next = this->curpos) == NULL) break;
  436.       }
  437.     np = np->next;
  438.   }
  439.   return success;
  440. }
  441.  
  442.  
  443. // set_intersection() -- Changes THIS list to contain everything that is an element
  444. //                   of both this and the specified CoolBase_List.
  445. // Input:            A reference to CoolBase_List.
  446. // Output:           None.
  447.  
  448. void CoolBase_List::set_intersection(const CoolBase_List& l) {
  449.   this->reset();                // make current position invalid
  450.   if (l.node_ptr == NULL)
  451.     this->clear();
  452.   else {
  453.     CoolBase_List_Node* np = this->node_ptr;
  454.     CoolBase_List_Node* prev_np = NULL;
  455.     CoolBase_List_Node* next_np;
  456.     while(np != NULL) {
  457.       CoolBase_List_Node* cp;
  458.       CoolBase_List_Node* pp;
  459.       if (!l.do_find(l.node_ptr, np->get_data(), cp, pp)) {
  460.         next_np = np->next;
  461.         if (prev_np == NULL) 
  462.       this->node_ptr = np->next;        // next node is at head
  463.         else 
  464.       prev_np->next = np->next;        // next node is in middle
  465.         this->reference(np->next);
  466.         this->dereference(np);            // delete np from this CoolBase_List.
  467.         np = next_np;                // set to next node to look at
  468.       }
  469.       else {
  470.         prev_np = np; 
  471.         np = np->next;
  472.       }
  473.     }
  474.   }
  475. }
  476.  
  477.  
  478. // set_union() -- Changes THIS list to contain everything that is an element of
  479. //             either THIS or the specified CoolBase_List
  480. // Input:      A reference to CoolBase_List.
  481. // Output:     None.
  482.  
  483. void CoolBase_List::set_union(const CoolBase_List& l) {
  484.   this->reset();                // make current position invalid
  485.   CoolBase_List_Node* tnode = this->node_ptr;
  486.   CoolBase_List_Node* lnode = l.node_ptr;
  487.   if (tnode ==  NULL && lnode != NULL) { 
  488.     this->node_ptr = lnode;            // this is empty, so set head node 
  489.     this->reference(lnode);            // of this to head node of l
  490.   }
  491.   else
  492.     for (; lnode !=NULL; lnode = lnode->next) {
  493.       CoolBase_List_Node* cp;
  494.       CoolBase_List_Node* pp;
  495.       if (!do_find(this->node_ptr, lnode->get_data(), cp, pp))
  496.     this->push(lnode->get_data());        // push new data of l into this.
  497.     }
  498. }
  499.  
  500.  
  501. // set_difference() -- Removes from THIS CoolBase_List the elements which also appears in
  502. //                 the specified CoolBase_List.
  503. // Input:          A reference to CoolBase_List.
  504. // Output:         None.
  505.  
  506. void CoolBase_List::set_difference(const CoolBase_List& l) {
  507.   this->reset();                // make current position invalid
  508.   if (l.node_ptr != NULL) {
  509.     CoolBase_List_Node* np = this->node_ptr;
  510.     CoolBase_List_Node* prev_np = NULL;
  511.     CoolBase_List_Node* next_np;
  512.     // if node in this CoolBase_List is found in CoolBase_List l, remove it from this CoolBase_List
  513.     while (np != NULL) {
  514.       CoolBase_List_Node* cp;
  515.       CoolBase_List_Node* pp;
  516.       if (l.do_find(l.node_ptr, np->get_data(), cp, pp)) {
  517.         next_np = np->next;
  518.         if (prev_np == NULL) 
  519.       this->node_ptr = np->next;        // Next node is at head
  520.         else 
  521.       prev_np->next = np->next;        // next node is in middle
  522.         this->reference(np->next);
  523.         this->dereference(np);            // delete np from this CoolBase_List.
  524.         np = next_np;                // set to next node to look at
  525.       }
  526.       else {
  527.         prev_np = np; 
  528.         np = np->next;
  529.       }
  530.     }
  531.   }
  532. }
  533.  
  534.  
  535. // set_xor() -- Changes CoolBase_List to contain those elements which appear in
  536. //                   exactly one of THIS CoolBase_List and the specified CoolBase_List.
  537. // Input:            A reference to CoolBase_List.
  538. // Output:           None.
  539.  
  540. void CoolBase_List::set_xor(const CoolBase_List& l) {
  541.   this->reset();    // make current position invalid
  542.   // first get copy of nodes in CoolBase_List l
  543.   CoolBase_List* lcopy = this->new_list((CoolBase_List_Node*)NULL);
  544.   lcopy->copy(l);
  545.   // remove elements in this CoolBase_List from copy of CoolBase_List l
  546.   lcopy->set_difference(*this);
  547.   // remove elements in CoolBase_List l from this CoolBase_List  
  548.   this->set_difference(l);
  549.   // append elements left in lcopy to end of this CoolBase_List
  550.   this->append(*lcopy);
  551.   delete lcopy;                    // destructor is virtual
  552. }
  553.  
  554. // next_intersection() -- Sets current position to next item in the
  555. //                        intersection of this CoolBase_List and the specified CoolBase_List.
  556. // Input:                 None.
  557. // Output:                TRUE if the next item exists,  FALSE otherwise.
  558.  
  559. Boolean CoolBase_List::next_intersection(const CoolBase_List& l) {
  560.   CoolBase_List_Node* np = this->curpos;
  561.   if (!this->traversal) {            // end of intersection
  562.     this->curpos = NULL;
  563.     return FALSE;
  564.   }
  565.   if (np == NULL)                // starting fresh
  566.     np = this->node_ptr;
  567.   else
  568.     np = np->next;                // increment position
  569.   for (; np != NULL; np = np->next) {
  570.     CoolBase_List_Node* cp;
  571.     CoolBase_List_Node* pp;
  572.     if (l.do_find(l.node_ptr, np->get_data(), cp, pp)) {
  573.       this->curpos = np;
  574.       return TRUE;
  575.     }
  576.   }
  577.   this->traversal = FALSE;            // now traversing second CoolBase_List
  578.   return FALSE;
  579. }
  580.  
  581.  
  582. // next_union() -- Sets current position to next item in the union of this
  583. //                  CoolBase_List and the specified CoolBase_List.
  584. // Input:           None.
  585. // Output:          TRUE if the next item exists,  FALSE otherwise.
  586.  
  587. Boolean CoolBase_List::next_union(const CoolBase_List& l) {
  588.   CoolBase_List_Node* np = this->curpos;
  589.   if (np == NULL && !this->traversal)        // end of both CoolBase_Lists
  590.     return FALSE;
  591.   if (np == NULL && this->traversal)        // starting fresh
  592.     np = this->node_ptr;
  593.   else  
  594.     if (np->next == NULL && this->traversal) {    // end of first CoolBase_List
  595.       this->traversal = FALSE;            // now traversing second CoolBase_List
  596.       np = l.node_ptr;
  597.     }
  598.   else
  599.     if (!this->traversal)  np = np->next;    // increment position
  600.  
  601.   if (this->traversal) {            // still in this CoolBase_List
  602.     if (this->curpos != NULL) 
  603.       this->curpos = np->next;    // increment current position
  604.     else this->curpos = np;
  605.     return TRUE;            
  606.   }
  607.  
  608.   for (; np != NULL; np = np->next) {
  609.     CoolBase_List_Node* cp;
  610.     CoolBase_List_Node* pp;
  611.     if (!do_find(this->node_ptr, np->get_data(), cp, pp)) {
  612.       this->curpos = np;
  613.       return TRUE;
  614.     }
  615.   }
  616.   return FALSE;
  617. }
  618.  
  619.  
  620. // next_difference() -- Sets current position to next item in the difference
  621. //                      of this CoolBase_List and the specified CoolBase_List
  622. // Input:               None.
  623. // Output:              TRUE if the next item exists,  FALSE otherwise.
  624.  
  625. Boolean CoolBase_List::next_difference(const CoolBase_List& l) {
  626.   CoolBase_List_Node* np = this->curpos;
  627.   if (np == NULL && !this->traversal) {      // end of this CoolBase_List
  628.     return FALSE;
  629.   }
  630.   if (np == NULL)                // starting fresh
  631.     np = this->node_ptr;
  632.   else {
  633.     this->traversal = FALSE;            // now traversing second CoolBase_List
  634.     np = np->next;                // incrementing position
  635.   }
  636.   for (; np != NULL; np = np->next) {
  637.     CoolBase_List_Node* cp;
  638.     CoolBase_List_Node* pp;
  639.     if (!l.do_find(l.node_ptr, np->get_data(), cp, pp)) {
  640.       this->curpos = np;
  641.       return TRUE;
  642.     }
  643.   }
  644.   return FALSE;
  645. }
  646.  
  647.  
  648. // next_xor() -- Sets current position to next item in exclusive_or
  649. //                        of this CoolBase_List and the specified CoolBase_List.
  650. // Input:                 None.
  651. // Output:                TRUE if the next item exists,  FALSE otherwise.
  652.  
  653. Boolean CoolBase_List::next_xor(const CoolBase_List& l) {
  654.   CoolBase_List_Node* cp;
  655.   CoolBase_List_Node* pp;
  656.   CoolBase_List_Node* np = this->curpos;
  657.   if (!this->traversal && np == NULL)        // end of both CoolBase_Lists
  658.     return FALSE;
  659.   if (np == NULL && this->traversal)        // starting fresh
  660.     np = this->node_ptr;
  661.   else 
  662.     if (np->next == NULL && this->traversal) {    // end of first CoolBase_List
  663.       this->traversal = FALSE;            // now traversing second CoolBase_List
  664.       np = l.node_ptr;
  665.     }
  666.   else
  667.     np = np->next;                // increment position
  668.   if (this->traversal) {            // still in this CoolBase_List
  669.     for (; np != NULL; np = np->next) 
  670.       if (!l.do_find(l.node_ptr, np->get_data(), cp, pp)) {
  671.         this->curpos = np;
  672.     return TRUE;            
  673.       } 
  674.     this->traversal = FALSE;            // now traversing second CoolBase_List
  675.     np = l.node_ptr; 
  676.   }
  677.   for (; np != NULL; np = np->next)
  678.     if (!do_find(this->node_ptr, np->get_data(), cp, pp)) {
  679.       this->curpos = np;
  680.       return TRUE;
  681.     }
  682.   return FALSE;
  683. }
  684.  
  685.  
  686. // describe() -- Describes internal structure of each node of this CoolBase_List
  687. // Input:        The output stream to display description on.
  688. // Output:       None.
  689.  
  690. void CoolBase_List::describe(ostream& os) {
  691.   os << "\nCoolBase_List " << this << ":\n";
  692.   int count = 0;
  693.   for (CoolBase_List_Node* np = this->node_ptr; np != NULL; np = np->next, count++) 
  694.   {
  695.     os << "Node" << count << ":\n";
  696.     os << " Data = ";
  697.     this->output_data(os,np);
  698.     os << "\n";
  699.     os << " Ref count = " << np->ref_count << "\n";
  700.   }
  701. }
  702.  
  703.  
  704. // operator<<() -- Overload output operator for CoolBase_List objects
  705. // Input:          An output stream reference and CoolBase_List reference
  706. // Output:         An output stream reference.
  707.  
  708. ostream& operator<<(ostream& os, const CoolBase_List& l) {
  709.   os << "(";
  710.   CoolBase_List_Node* np = l.node_ptr;
  711.   if (np != NULL) {
  712.     l.output_data(os, np);
  713.     for (np = np->next; np != NULL; np = np->next) {
  714.       os << " ";
  715.       l.output_data(os,np);
  716.     }
  717.   }
  718.   return os << ")";
  719. }
  720.  
  721.  
  722. // new_list() -- Returns new CoolBase_List with head node initialized to specified node
  723. // Input:        The node pointer.
  724. // Output:       A pointer to the new CoolBase_List.
  725.  
  726. CoolBase_List* CoolBase_List::new_list(CoolBase_List_Node*) {
  727. #if ERROR_CHECKING
  728.   //RAISE Warning, SYM(CoolBase_List_Node), SYM(Redundant_Method_Call),
  729.   printf ("CoolBase_List_Node::new_list(): Method called is redundant.\n");
  730. #endif
  731.   return (CoolBase_List*)NULL;  
  732. }
  733.  
  734.  
  735. // insert_before_node() -- Inserts a new node before the specified node.
  736. // Input:                  A Type reference and a Node pointer.
  737. // Output:                 A pointer to the new node.
  738.  
  739. CoolBase_List_Node* CoolBase_List::insert_before_node(const void*, CoolBase_List_Node*) {
  740. #if ERROR_CHECKING
  741.   //RAISE Warning, SYM(CoolBase_List_Node), SYM(Redundant_Method_Call),
  742.   printf ("CoolBase_List_Node::insert_before_node(): Method called is redundant.\n");
  743. #endif
  744.  return NULL;
  745. }
  746.  
  747.  
  748. // insert_after_node() -- Inserts a new node after the specified node.
  749. // Input:                 A Type reference and a Node pointer.
  750. // Output:                A pointer to the new node.
  751.  
  752. CoolBase_List_Node* CoolBase_List::insert_after_node(const void*, CoolBase_List_Node*) const {
  753. #if ERROR_CHECKING
  754.   //RAISE Warning, SYM(CoolBase_List_Node), SYM(Redundant_Method_Call),
  755.   printf ("CoolBase_List_Node::insert_after_node(): Method called is redundant.\n");
  756. #endif
  757.  return NULL;
  758. }
  759.  
  760.  
  761. // compare_data() -- Compares data using default compare function of this CoolBase_List
  762. // Input:            Two const void* pointers which will be type cast.
  763. // Output:           None.
  764.  
  765. Boolean CoolBase_List::compare_data(const void*, const void*) const {
  766. #if ERROR_CHECKING
  767.   //RAISE Warning, SYM(CoolBase_List_Node), SYM(Redundant_Method_Call),
  768.   printf ("CoolBase_List_Node::compare_data(): Method called is redundant.\n");
  769. #endif
  770.   return FALSE;
  771. }
  772.  
  773.  
  774. // output_data()  -- Outputs node data from specified stream.
  775. // Input:            An output stream reference and node pointer.
  776. // Output:           A void* pointer of data.
  777.  
  778. void CoolBase_List::output_data(ostream&, const CoolBase_List_Node*) const {
  779.  
  780. #if ERROR_CHECKING
  781.   //RAISE Warning, SYM(CoolBase_List_Node), SYM(Redundant_Method_Call),
  782.   printf ("CoolBase_List_Node::output_data(): Method called is redundant.\n");
  783. #endif
  784. }
  785.  
  786.  
  787. // copy_nodes() -- Returns a copy of nodes in THIS CoolBase_List.
  788. // Input:          NONE.
  789. // Output:         The first node pointer of copy.
  790.  
  791. CoolBase_List_Node* CoolBase_List::copy_nodes() const {
  792.   CoolBase_List_Node *np, *first_np;
  793.   if ((np = this->node_ptr) == NULL)  
  794.      first_np = NULL;
  795.   else {
  796.     // copy first node of this CoolBase_List
  797.     first_np = this->insert_after_node(np->get_data(), NULL);
  798.     CoolBase_List_Node* rest_np = first_np;
  799.  
  800.     // copy rest of nodes of this CoolBase_List
  801.     for (np = np->next; np != NULL; np = np->next) {
  802.       rest_np = this->insert_after_node(np->get_data(), rest_np);
  803.     }
  804.   }
  805.   return first_np;
  806. }
  807.  
  808.  
  809. void CoolBase_List::free_nodes(CoolBase_List_Node* np) {
  810.   do {
  811.     if (np->ref_count < 0) {
  812.       cout << "\nWarning: negative ref count of " << np->ref_count;
  813.       cout << " for data ";
  814.       this->output_data(cout, np);
  815.       cout << " and ";
  816. #if GENERIC_TYPECHECK
  817.       cout << (this->type_of())->name() << " = ";
  818. #endif
  819.       cout << this << ".\n";
  820.     } 
  821.     // no longer sharing this node with other CoolBase_Lists
  822.     CoolBase_List_Node* next_np = np->next;     // save pointer to next node
  823.     np->next = NULL;
  824. //  delete np->data;                // not nec. data is ptr or obj
  825.     delete np;                    // delete node structure
  826.     np = next_np;                // check reference of next node
  827.   }
  828.   while (np != NULL && --(np->ref_count) <= 0);
  829. }
  830.  
  831. // operator= -- Assigns THIS to the specified CoolBase_List.
  832. // Input:       A reference to a CoolBase_List which THIS will be assigned to.
  833. // Output:      The modified THIS.
  834.  
  835. CoolBase_List* CoolBase_List::operator=(const CoolBase_List& l) {
  836.   this->reset();                // make current position invalid
  837.   this->reference(l.node_ptr);            // will point to new stuff
  838.   this->dereference(this->node_ptr);        // delete old stuff
  839.   this->node_ptr = l.node_ptr;
  840.   return this;
  841. }
  842.  
  843.  
  844. // operator[]() -- Returns the nth node of this CoolBase_List
  845. // Input:          A positive integer index.
  846. // Output:         A pointer to the nth node.
  847.  
  848. CoolBase_List_Node* CoolBase_List::operator[] (int n) {
  849.   int count = n;
  850.   for (CoolBase_List_Node *np = this->node_ptr, *prev_np = NULL;
  851.       np != NULL && count > 0;
  852.       prev_np = np, np = np->next, count--);
  853.  
  854.   // if n<length,  found nth node
  855.   if (np != NULL && count == 0) {
  856.     this->curpos = np;
  857.     this->prevpos = prev_np;
  858.     return np;
  859.   }
  860.   else return (CoolBase_List_Node*)NULL;  // or error
  861. }
  862.  
  863.  
  864. // position() -- Returns the position of the specified data item in this CoolBase_List,
  865. //               else returns -1 if not found
  866. // Input:        A void* pointer of a data item.
  867. // Output:       The integer position.
  868.  
  869. int CoolBase_List::position(const void* x) {
  870.   int index = 0;
  871.   // NOTE: It's faster to call do_find, then count the position,
  872.   // than to do the search ourselves using compare_data and get_data.
  873.   if(!this->do_find(this->node_ptr, x, this->curpos, this->prevpos))
  874.     return -1;
  875.   else {
  876.     int index = 0;
  877.     CoolBase_List_Node* cp = this->curpos;
  878.     CoolBase_List_Node* np = this->node_ptr;
  879.     while (np != cp) np = np->next, index++;
  880.     return index;
  881.   }
  882. }
  883.  
  884.  
  885. // do_find() -- Returns TRUE if the specified element is a member of THIS CoolBase_List.
  886. // Input:       A void* pointer of data item to be searched.
  887. // Output:      TRUE or FALSE.
  888.  
  889. Boolean CoolBase_List::do_find(CoolBase_List_Node*, const void*,
  890.               CoolBase_List_Node*&, CoolBase_List_Node*&) const {
  891.   cout << "\nWarning:  CoolBase_List_Node::find(x) has been called.\n";
  892.   return FALSE;
  893. }
  894.  
  895. // member() -- Returns TRUE if THIS CoolBase_List contains the specified element and
  896. //             sets the specified CoolBase_List to a subList in THIS CoolBase_List starting
  897. //             at the first occurence of element.
  898. // Input:      A reference to the CoolBase_List which will be set to a subCoolBase_List within
  899. //             THIS CoolBase_List, and a void* pointer of data item to be searched.
  900. // Output:     A CoolBase_List pointer to some tail of THIS.
  901.  
  902. Boolean CoolBase_List::member(CoolBase_List& l,const void* x) {
  903.   this->dereference(l.node_ptr);
  904.   if (this->do_find(this->node_ptr, x, this->curpos, this->prevpos)) {
  905.     this->reference(this->curpos);
  906.     l.node_ptr = this->curpos;
  907.     return TRUE;
  908.   } else {
  909.     l.node_ptr = NULL;
  910.     return FALSE;
  911.   }
  912. }
  913.  
  914.  
  915. // push() -- Prepends the specified data item to the front of CoolBase_List
  916. // Input:    A void* pointer of the data item to be prepended.
  917. // Output:   Always TRUE.
  918.  
  919. Boolean CoolBase_List::push(const void* x) {
  920.   this->curpos = this->insert_before_node(x, this->node_ptr);
  921.   this->node_ptr = this->curpos;
  922.   this->prevpos = NULL;
  923.   return TRUE;
  924. }
  925.  
  926.  
  927. // push_new() -- Pushes a new element at head of THIS CoolBase_List if it is not already
  928. //               a member of the CoolBase_List.
  929. // Input:        A void* pointer of new data.
  930. // Output:       TRUE if item not on CoolBase_List, FALSE otherwise.
  931.  
  932. Boolean CoolBase_List::push_new(const void* x) {
  933.   CoolBase_List_Node* cp;
  934.   CoolBase_List_Node* pp;
  935.   if (!this->do_find(this->node_ptr, x, cp, pp)) // don't change curpos
  936.     return push(x);
  937.   else
  938.     return FALSE;
  939. }
  940.  
  941.  
  942. // push_end() -- Appends the specified data item to the end of this CoolBase_List
  943. // Input:        A void* pointer of the data item to be appended.
  944. // Output:       Always TRUE.
  945.  
  946. Boolean CoolBase_List::push_end(const void* x) {
  947.   CoolBase_List_Node* last_np = this->node_ptr;
  948.   if (last_np == NULL) {  
  949.     // there arn't any nodes in this CoolBase_List; x will be the head node
  950.     this->node_ptr = this->curpos = this->insert_after_node(x, NULL);
  951.     this->prevpos = NULL;
  952.   }
  953.   else {
  954.     CoolBase_List_Node* cp = this->curpos;
  955.     // find last node of this CoolBase_List
  956.     if (cp != NULL && cp->next == NULL)
  957.       last_np = cp;
  958.     else
  959.       while(last_np->next != NULL) last_np = last_np->next;
  960.     // insert x after last node
  961.     this->curpos = this->insert_after_node(x, last_np);  
  962.     this->prevpos = last_np;
  963.   }
  964.  return TRUE;
  965. }
  966.  
  967.  
  968. // push_end_new() -- Pushes a new element at end of THIS CoolBase_List if it is not
  969. //                   already a member of the CoolBase_List.
  970. // Input:            A void* pointer of new data.
  971. // Output:           TRUE if item not on CoolBase_List, FALSE otherwise.
  972.  
  973. Boolean CoolBase_List::push_end_new(const void* x) {
  974.   if (!this->do_find(this->node_ptr, x, this->curpos, this->prevpos))
  975.     return this->push_end(x);
  976.   else
  977.     return FALSE;
  978. }
  979.  
  980.  
  981. // pop() -- Removes and returns head element of THIS CoolBase_List.
  982. // Input:   None.
  983. // Output:  Node pointer containing head data element of THIS CoolBase_List.
  984.  
  985. CoolBase_List_Node* CoolBase_List::pop() {
  986.   CoolBase_List_Node* old_head = this->node_ptr;
  987.   if (old_head != NULL) {
  988.     this->reset();                // make current position invalid
  989.     this->node_ptr = old_head->next;
  990.     this->reference(old_head->next);
  991.     return old_head;
  992.   }
  993.   else return NULL;
  994. }
  995.  
  996.  
  997. // remove() -- Removes item at current position.
  998. // Input:      None.
  999. // Output:     The node pointer of item removed.
  1000.  
  1001. CoolBase_List_Node*  CoolBase_List::remove() {
  1002.   if (this->curpos == NULL)
  1003.     return NULL;
  1004.   CoolBase_List_Node* np = this->prevpos;
  1005.   CoolBase_List_Node* cp = this->curpos;
  1006.   if (np == NULL || np->next != cp) { 
  1007.     np  = this->node_ptr;
  1008.     if (np == cp) {                // node to remove is head node
  1009.       this->curpos = np->next;
  1010.       this->node_ptr = np->next;        // this points to next of head
  1011.       this->reference(np->next);        
  1012.       return np;
  1013.     }
  1014.     // find previous node current position
  1015.     while (np != NULL && np->next != this->curpos) np = np->next;
  1016.     if (np == NULL) return NULL;        // error: curpos was not in list
  1017.     else this->prevpos = np;
  1018.   }
  1019.   np->next = cp->next;
  1020.   this->curpos = cp->next;
  1021.   this->reference(cp->next);
  1022.   return cp;
  1023. }
  1024.  
  1025.  
  1026. // remove() -- Removes the first occurence of the specified item in this CoolBase_List
  1027. // Input:      A refernce to data item to be removed.
  1028. // Output:     TRUE if item found and removed, FALSE otherwise.
  1029.  
  1030. Boolean CoolBase_List::remove(const void* x) {
  1031.   // find node for x
  1032.   if (this->do_find(this->node_ptr, x, this->curpos, this->prevpos)) {
  1033.     this->dereference(this->remove());        // throw node to trash, since 
  1034.     return TRUE;                // it is not returned
  1035.   }
  1036.   return FALSE;
  1037. }
  1038.  
  1039.  
  1040. // replace() -- Replaces the first occurence of specified data item in THIS
  1041. //              CoolBase_List with a new value
  1042. // Input:       Two void* pointers.
  1043. // Output:      TRUE if item found and replaced, FALSE otherwise.
  1044.  
  1045. Boolean CoolBase_List::replace(const void* old_data, const void* new_data) {
  1046.   // find node of old_data in this CoolBase_List
  1047.   if(this->do_find(this->node_ptr, old_data, this->curpos, this->prevpos)) {
  1048.     // replace old_data in node with new_data
  1049.     this->curpos->set_data(new_data);
  1050.     return TRUE;
  1051.   }
  1052.   return FALSE;
  1053. }
  1054.  
  1055.  
  1056. // replace_all() -- Replaces all occurences of the specified data item in THIS
  1057. //                  CoolBase_List with a new value.
  1058. // Input:           Two void* pointers.
  1059. // Output:          TRUE if at least one item found and replaced, else FALSE
  1060.  
  1061. Boolean CoolBase_List::replace_all(const void* old_data, const void* new_data) {
  1062.   this->reset();    // make current position invalid
  1063.   Boolean success = FALSE; // return value
  1064.   CoolBase_List_Node* pp;
  1065.   CoolBase_List_Node* np = this->node_ptr;
  1066.   while (np != NULL && this->do_find(np, old_data, np, pp)) {
  1067.     np->set_data(new_data);
  1068.     success = TRUE;
  1069.     np = np->next;
  1070.   }
  1071.   return success;
  1072. }
  1073.  
  1074.  
  1075. // sort() -- Sorts the elements of THIS using the specified predicate function.
  1076. //           The predicate function returns TRUE if and only if the first
  1077. //           element preceeds the second. The sort routine uses the Sort
  1078. //           algorithm as given in "Numerical Recipes in C" p247.
  1079. // Input:    A predicate function pointer.
  1080. // Output:   None.
  1081.  
  1082. void CoolBase_List::sort(Predicate f) {
  1083.   this->reset();    // make current position invalid
  1084.   CoolBase_List_Node* np;
  1085.   int l, j, ir, i;
  1086.   int n = this->length();
  1087.   if (n < 2) return;    // No sense sorting if less than two elements
  1088.   CoolBase_List_Node** node_array = new CoolBase_List_Node*[n+1];
  1089.   // put the nodes of THIS into an array which will be used by the
  1090.   // heap sort algorithm
  1091.   for (np = this->node_ptr, i = 1; np != NULL; np = np->next, i++)
  1092.      node_array[i] = np;
  1093.   // the heap sort algorithm
  1094.   CoolBase_List_Node* temp;
  1095.   l = (n >> 1) + 1;
  1096.   ir = n;
  1097.   while (TRUE) {
  1098.     if (l > 1)
  1099.       temp = node_array[--l];
  1100.     else {
  1101.       temp = node_array[ir];
  1102.       node_array[ir] = node_array[1];
  1103.       if (--ir == 1) {
  1104.     node_array[1] = temp;
  1105.     break;
  1106.       }
  1107.     }
  1108.     i = l;
  1109.     j = i << 1;
  1110.     while (j <= ir) {
  1111.       if (j < ir && (*f) ((node_array[j])->get_data(),
  1112.               (node_array[j+1])->get_data()) < 0)
  1113.     ++j;
  1114.       if ((*f) (temp->get_data(), (node_array[j])->get_data()) < 0) {
  1115.     node_array[i] = node_array[j];
  1116.     j += (i = j);
  1117.       }
  1118.       else
  1119.     j = ir + 1;
  1120.     }
  1121.     node_array[i] = temp;
  1122.   }
  1123.  
  1124.   // put the sorted nodes of the array back into THIS
  1125.   this->node_ptr = node_array[1];
  1126.   for (i = 1; i < n; i++) {
  1127.      (node_array[i])->next = node_array[i+1];
  1128.    }
  1129.   (node_array[n])->next = NULL;
  1130.  
  1131.   delete [] node_array;
  1132. }
  1133.  
  1134.  
  1135. // merge() -- Merges the elements of THIS CoolBase_List with the elements of the
  1136. //            specified CoolBase_List sorted with the specified predicate function.
  1137. //            If THIS is sorted already, then the result of the merge will be
  1138. //            sorted. Otherwise there are no guarantees for the sortedness of
  1139. //            the result.
  1140. // Input:     A reference to a CoolBase_List to be merged and a predicate function 
  1141. //            pointer.
  1142. // Output:    None.
  1143.  
  1144. void CoolBase_List::merge(const CoolBase_List& l, Predicate f) {
  1145.   this->reset();    // make current position invalid
  1146.   CoolBase_List_Node* tnode = this->node_ptr;
  1147.   if (tnode == NULL)
  1148.     // if this CoolBase_List is NULL, just assign this CoolBase_List to CoolBase_List l
  1149.     this->operator=(l);
  1150.   else {
  1151.     // begin merging CoolBase_List l into this CoolBase_List
  1152.     CoolBase_List_Node *lnode;
  1153.  
  1154.     // first merge nodes of CoolBase_List l in front of first node of this CoolBase_List
  1155.     // until a node in this CoolBase_List is less than a node in CoolBase_List l
  1156.     for (lnode = l.node_ptr;
  1157.      lnode != NULL &&
  1158.      (*f) (tnode->get_data(), lnode->get_data()) >= 0;
  1159.      lnode = lnode->next) {
  1160.       tnode = this->insert_before_node(lnode->get_data(), tnode);
  1161.       this->node_ptr = tnode;
  1162.     }
  1163.       
  1164.     // merge rest of nodes in CoolBase_List l into this CoolBase_List
  1165.     CoolBase_List_Node* tnode_prev = tnode;
  1166.     tnode = tnode->next;
  1167.     while (lnode != NULL) {
  1168.       if (tnode == NULL) {
  1169.     // if the end of THIS is reached, 
  1170.     // add the CoolBase_List l nodes to the end of this CoolBase_List
  1171.     for (; lnode !=NULL; lnode = lnode->next)
  1172.       tnode_prev = this->insert_after_node(lnode->get_data(), tnode_prev);
  1173.       }
  1174.       else if ((*f)(tnode->get_data(), lnode->get_data()) < 0) {
  1175.     // if node in this CoolBase_List is less than node in CoolBase_List l
  1176.     // just go to next node in this CoolBase_List
  1177.     tnode_prev = tnode;
  1178.     tnode = tnode->next;      
  1179.       } else {
  1180.     // if node in CoolBase_List l is less than node in this CoolBase_List
  1181.     // insert the CoolBase_List l node into THIS
  1182.     // and goto next node in CoolBase_List l
  1183.     tnode_prev->next = this->insert_before_node(lnode->get_data(), tnode);
  1184.     tnode_prev = tnode_prev->next;
  1185.     lnode = lnode->next;
  1186.       }
  1187.     }
  1188.   }
  1189. }
  1190.  
  1191.  
  1192. // insert_before() -- Inserts the specified item before the current position
  1193. // Input:             A void* pointer.
  1194. // Output:            TRUE if current position is valid, FALSE otherwise.
  1195.  
  1196. Boolean CoolBase_List::insert_before(const void* new_item) {
  1197.   CoolBase_List_Node* cp = this->curpos;
  1198.   CoolBase_List_Node *np = this->prevpos;
  1199.   if (cp == NULL)
  1200.     return FALSE;
  1201.   if (np == NULL || np->next != cp) {
  1202.     np = this->node_ptr;
  1203.     // current position is head node    
  1204.     if (np == cp)
  1205.       return this->push(new_item);
  1206.     // find previous node of current position in CoolBase_List
  1207.     while (np != NULL && np->next != cp) np = np->next;
  1208.     if (np == NULL)
  1209.       return FALSE;  // couldn't find current position
  1210.     else
  1211.       this->prevpos = np;
  1212.   }
  1213.   // insert new_item before current position and
  1214.   // set current position to this new node
  1215.   this->curpos = this->insert_before_node(new_item, cp);
  1216.   np->next = this->curpos;
  1217.   return TRUE;
  1218. }
  1219.  
  1220.  
  1221. // insert_after() -- Inserts the specified item after the current position
  1222. // Input:            A void* pointer.
  1223. // Output:           TRUE if current position is valid, FALSE otherwise.
  1224.  
  1225. Boolean CoolBase_List::insert_after(const void* new_item) {
  1226.   if (this->curpos == NULL)
  1227.     return FALSE;
  1228.   this->prevpos = this->curpos;
  1229.   this->curpos = this->insert_after_node(new_item,
  1230.                            this->curpos);
  1231.   return TRUE;
  1232. }
  1233.  
  1234.  
  1235. // insert_before() -- Inserts the specified new item before the specified
  1236. //                    target item in this CoolBase_List
  1237. // Input:             Two data void* pointers.
  1238. // Output:            TRUE if target item found, FALSE otherwise.
  1239.  
  1240. Boolean CoolBase_List::insert_before(const void* new_item, const void* target_item) {
  1241.   // find node with target item
  1242.   if (this->do_find(this->node_ptr, target_item, this->curpos, this->prevpos)){
  1243.     CoolBase_List_Node *np = this->curpos;
  1244.     CoolBase_List_Node *prev_np = this->prevpos;
  1245.     // insert new item before target item
  1246.     this->curpos = this->insert_before_node(new_item, np);
  1247.     if (prev_np == NULL)
  1248.       this->node_ptr = this->curpos;     // new item is the head node
  1249.     else
  1250.       prev_np->next = this->curpos; // new item is a  middle node
  1251.     return TRUE;
  1252.   }
  1253.   return FALSE;
  1254. }
  1255.  
  1256.  
  1257. // insert_after() -- Inserts the specified new item after the specified target
  1258. //                   item in this CoolBase_List
  1259. // Input:            Two data void* pointers.
  1260. // Output:           TRUE if target item found, FALSE otherwise.
  1261.  
  1262. Boolean CoolBase_List::insert_after(const void* new_item, const void* target_item) {
  1263.   // find node with target item
  1264.   CoolBase_List_Node *np;
  1265.   if (this->do_find(this->node_ptr, target_item, np, this->prevpos)) {
  1266.     this->curpos = this->insert_after_node(new_item, np);
  1267.     this->prevpos = np;
  1268.     return TRUE;
  1269.   }       
  1270.   return FALSE;
  1271. }
  1272.  
  1273.  
  1274. // value_error -- Raise exception for CoolBase_List::value() method
  1275. // Input:         Type string
  1276. // Output:        None
  1277.  
  1278. void CoolBase_List::value_error (const char* Type) {
  1279.   //RAISE Error, SYM(CoolBase_List), SYM(Invalid_Cpos),
  1280.   printf ("CoolList<%s>::value(): Invalid current position.\n", Type);
  1281.   abort ();
  1282. }
  1283.  
  1284.  
  1285. // get_error -- Raise exception for CoolBase_List::get() method
  1286. // Input:       Type string
  1287. // Output:      None
  1288.  
  1289. void CoolBase_List::get_error (const char* Type, int n) {
  1290.   //RAISE Error, SYM(CoolBase_List), SYM(Negative_Index),
  1291.   printf ("CoolList<%s>::get(): Negative index %d.\n", Type, n);
  1292.   abort ();
  1293. }
  1294.  
  1295.  
  1296. // before_error -- Raise exception for CoolBase_List::insert_before() method
  1297. // Input:          Type string
  1298. // Output:         None
  1299.  
  1300. void CoolBase_List::before_error (const char* Type) {
  1301.   //RAISE Error, SYM(CoolBase_List), SYM(Invalid_Cpos),
  1302.   printf ("CoolList<%s>::insert_before(): Invalid current position.\n", Type);
  1303.   abort ();
  1304. }
  1305.  
  1306.  
  1307. // after_error -- Raise exception for CoolBase_List::insert_after() method
  1308. // Input:         Type string
  1309. // Output:        None
  1310.  
  1311. void CoolBase_List::after_error (const char* Type) {
  1312.   //RAISE Error, SYM(CoolBase_List), SYM(Invalid_Cpos),
  1313.   printf ("CoolList<%s>::insert_after(): Invalid current position.\n", Type);
  1314.   abort ();
  1315. }
  1316.  
  1317.  
  1318. // bracket_error -- Raise exception for CoolBase_List::operator[]() method
  1319. // Input:           Type string
  1320. // Output:          None
  1321.  
  1322. void CoolBase_List::bracket_error (const char* Type, int n) {
  1323.   //RAISE Error, SYM(CoolBase_List), SYM(Negative_Index),
  1324.   printf ("CoolList<%s>::operator[](): Negative index %d.\n", Type, n);
  1325.   abort ();
  1326. }
  1327.  
  1328.  
  1329. // pop_error -- Raise exception for CoolBase_List::pop() method
  1330. // Input:       Type string
  1331. // Output:      None
  1332.  
  1333. void CoolBase_List::pop_error (const char* Type) {
  1334.   //RAISE Error, SYM(CoolBase_List), SYM(No_Elements),
  1335.   printf ("CoolList<%s>::pop(): No elements in CoolBase_List.\n", Type);
  1336.   abort ();
  1337. }
  1338.  
  1339.  
  1340. // remove_error -- Raise exception for CoolBase_List::remove() method
  1341. // Input:          Type string
  1342. // Output:         None
  1343.  
  1344. void CoolBase_List::remove_error (const char* Type) {
  1345.   //RAISE Error, SYM(CoolBase_List), SYM(Invalid_Cpos),
  1346.   printf ("CoolList<%s>::remove(): Invalid current position.\n", Type);
  1347.   abort ();
  1348. }
  1349.  
  1350. // va_arg_error -- Raise exception for using class objects, or chars in (...)
  1351. // Input:          Type string
  1352. // Output:         None
  1353.  
  1354. void CoolBase_List::va_arg_error (const char* Type, int n) {
  1355.   //RAISE Error, SYM(CoolBase_List), SYM(Invalid_Va_Arg),
  1356.   printf ("CoolList<%s>::CoolList<%s>(): Invalid type in ... or wrong alignment with %d bytes.\n",
  1357.       Type, Type, n);
  1358.   abort ();
  1359. }
  1360.  
  1361.  
  1362.